package com.atguigu.search;

import java.util.Arrays;

/**
 * @author 龍
 * 插值查找：mid=low+(key-a[low])*(high-low)/(a[high]-a[low])。mid的定位比较快。
 * 注意：数据量比较大，关键字分布比较均匀，效率比较高。
 * 由 mid=left+(findVal-arr[left])*(right-left)/(arr[right]-arr[left]);需要注意可能会发生越界。
 */
public class InsertSearch {
    public static void main(String[] args) {
        int[] array=new int[100];
        for (int i = 0; i < 100; i++) {
            array[i]=i+1;
        }
        System.out.println(Arrays.toString(array));
        System.out.println("insert====="+insertSearch(array,0,array.length-1,50));

    }
    /**
     *插值查找算法
     */
    public static int insertSearch(int[] arr,int left,int right,int findVal){
        System.out.println("-------------------------");
        if(left>right||findVal<arr[0]||findVal>arr[arr.length-1]){
            return -1;
        }
        //求出mid
        int mid=left+(findVal-arr[left])*(right-left)/(arr[right]-arr[left]);
        if (findVal>arr[mid]){
            insertSearch(arr,mid+1,right,findVal);
        }else if (findVal<arr[mid]){
            insertSearch(arr,left,mid-1,findVal);
        }else {
            return mid;
        }
        return -1;
    }

}
